COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00034 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a17.tex[162,phy] \today\hfill}

\parskip 5pt
\bigskip
\line{\bf Combinatorics by Counting Functions\hfil}

\bigskip
Let $X$ and $Y$ be finite ordered sets, where $|X|=n$, $|Y|=k$. Whenever
convenient, we will take $X={\bf n}=\{\,x\mid 0<x≤n\,\}$, $Y={\bf k}$;
${\bf 0}=\emptyset$. Define {\bf a+b} $=\{\,x\mid 0<x≤a+b\,\}$.
Let $F=(X→Y)$, the set of functions from $X$ to~$Y$. If $f\in F$, 
${\rm ran}\;f=f(X)$, ${\rm dom}\;f=X$. If 
$Y=Y↓1\uplus Y↓2$ (disjoint union),
$X↓1=f↑{-1}(Y↓1)$, $X↓2=f↑{-1}(Y↓2)$, then 
$X↓1\pluss X↓2=X$; any partition of~$Y$ induces a partition of~$X$.

The fundamental combinatorial functions we shall study are:

\smallskip
\display 20pt:$\bullet$:
$a!$, the number of bijections from {\bf a} to~{\bf a}.
For example, $4!=24$.

\smallskip
\display 20pt:$\bullet$:
${a\choose b}$, the number of subsets of {\bf a} with cardinality~$b$.
For example, ${4\choose 2}=6$, the subsets of {\bf 4} being
$\{1,2\}$, $\{1,3\}$, $\{1,4\}$, $\{2,3\}$, $\{2,4\}$, $\{3,4\}$.
Because the subsets of~{\bf a} with cardinality~$b$ are in one-to-one
correspondence with their complements, of cardinality $a-b$, 
${a\choose b}={a\choose a-b}$.

\smallskip
\display 20pt:$\bullet$:
$k↑{\underline{n}}$ is the number of one-to-one functions (injections) from~{\bf n}
to~{\bf k}. For example, $4↑{\underline{2}}=12$.

\smallskip
\display 20pt:$\bullet$:
$\{{n\atop k}\}$ is the number of partitions of~{\bf n} into 
$k$ nonempty subsets. For example, $\{{4\atop 2}\}=7$.
We call $\{{n\atop k}\}$ a Stirling partition number.

\smallskip
\display 20pt:$\bullet$:
$[{n\atop k}]$ is the number of permutations of~{\bf n} with exactly
$k$~cycles. For example, $[{4\atop 2}]=11$. We call
$[{n\atop k}]$ a Stirling cycle number.

\smallskip
\display 20pt:$\bullet$:
$\delta↓{ab}$ is 1 if $a=b$, 0 otherwise.

\smallskip
Some important subsets of $F$, for which we want to determine the cardinalities,
are:

\smallskip
\display 40pt::
$F↓{\rm all}=F$.

\display 40pt::
$F↓{\rm inj}$, the set of one-to-one (injective) functions.

\display 40pt::
$F↓{\rm sur}$, the set of onto (surjective) functions.

\display 40pt::
$F↓{\rm bij}$, the set of one-to-one and onto (bijective) functions.

\display 40pt::
$F↓{\rm mon}$, the set of monotone non-decreasing functions; 
 $x↓1≤x↓2$ implies $f(x↓1)≤f(x↓2)$.

\display 40pt::
$F↓{\rm strict}$, the set of one-to-one (strictly) monotone functions;
 $x↓1<x↓2$ implies $f(x↓1)<f(x↓2)$.

\display 40pt::
$F↓{\rm step}$, the set of onto monotone functions, for which
 $f(1)=1$, $f(n)=k$, $f(x+1)-f(x)\in\{0,1\}$.

\display 40pt::
$F↓{\rm iso}$, the set of order-preserving isomorphisms.

\smallskip
The cardinality of $F$ is designated by $\#↓{\rm all}(n,k)$; the cardinalities
of the subsets are $\#↓{\rm inj}(n,k)$, $\#↓{\rm sur}(n,k)$, etc.
When context is unambiguous, subscripts will be omitted.

When $n=0$, the only function in $F$ is the totally undefined function,
the empty set of ordered pairs. That function is one-to-one and monotone,
but is only onto if $k=0$. Therefore $\#(0,0)=1$ for all subscripts.
For $k>0$, $\#(0,k)=1$ for subscripts all, inj, mon, and strict;
$\#(0,k)=0$ for subscripts sur, bij, step, and iso.
For $n>0$, $k=0$, there are no functions in $F$, so $\#(n,0)=0$ for all
subscripts. For $n>0$, $k=1$, $F$~is the monotone onto
function that maps every argument
into~1. It is not one-to-one unless $n=1$. These
facts determine $\#(n,k)$ for all subscripts if $n=0$, $k=0$, or $k=1$:

$$\vbox{\offinterlineskip
\halign{$#$&$#$&$#$%\quad
&\vrule#&\strut\quad$#$&\quad$#$&\quad$#$&\quad$#$&\quad$#$&\quad$#$&\quad$#$\quad\cr
&&&\omit&\multispan7\hfil$\#↓{\rm all}$, $\#↓{\rm mon}$\hfil\cr
&&k\cr
n&&&\omit&0&1&2&3&4&5&6\cr
&&&\omit&\multispan7\hrulefill\cr
&&&height2pt\cr
&0&&&1&1&1&1&1&1&1\cr
&1&&&0&1\cr
&2&&&0&1\cr
&3&&&0&1\cr
&4&&&0&1\cr
&5&&&0&1\cr
&6&&&0&1\cr
}}\qquad
\vbox{\offinterlineskip
\halign{$#$&$#$&$#$%\quad
&\vrule#&\strut\quad$#$&\quad$#$&\quad$#$&\quad$#$&\quad$#$&\quad$#$&\quad$#$\quad\cr
&&&\omit&\multispan7\hfil$\#↓{\rm sur}$, $\#↓{\rm step}$\hfil\cr
&&k\cr
n&&&\omit&0&1&2&3&4&5&6\cr
&&&\omit&\multispan7\hrulefill\cr
&&&height2pt\cr
&0&&&1&0&0&0&0&0&0\cr
&1&&&0&1\cr
&2&&&0&1\cr
&3&&&0&1\cr
&4&&&0&1\cr
&5&&&0&1\cr
&6&&&0&1\cr
}}$$

$$\vbox{\offinterlineskip
\halign{$#$&$#$&$#$%\quad
&\vrule#&\strut\quad$#$&\quad$#$&\quad$#$&\quad$#$&\quad$#$&\quad$#$&\quad$#$\quad\cr
&&&\omit&\multispan7\hfil$\#↓{\rm inj}$, $\#↓{\rm strict}$\hfil\cr
&&k\cr
n&&&\omit&0&1&2&3&4&5&6\cr
&&&\omit&\multispan7\hrulefill\cr
&&&height2pt\cr
&0&&&1&1&1&1&1&1&1\cr
&1&&&0&1\cr
&2&&&0&0\cr
&3&&&0&0\cr
&4&&&0&0\cr
&5&&&0&0\cr
&6&&&0&0\cr
}}\qquad
\vbox{\offinterlineskip
\halign{$#$&$#$&$#$%\quad
&\vrule#&\strut\quad$#$&\quad$#$&\quad$#$&\quad$#$&\quad$#$&\quad$#$&\quad$#$\quad\cr
&&&\omit&\multispan7\hfil$\#↓{\rm bij}$, $\#↓{\rm iso}$\hfil\cr
&&k\cr
n&&&\omit&0&1&2&3&4&5&6\cr
&&&\omit&\multispan7\hrulefill\cr
&&&height2pt\cr
&0&&&1&0&0&0&0&0&0\cr
&1&&&0&1\cr
&2&&&0&0\cr
&3&&&0&0\cr
&4&&&0&0\cr
&5&&&0&0\cr
&6&&&0&0\cr
}}$$

Partition {\bf k} into $Y↓1\uplus Y↓2$, where $|Y↓1|=i$, $|Y↓2|=j$,
$Y↓1<Y↓2$, $i+j=k$. If $f$ is monotone, 
$X↓1=f↑{-1}(Y↓1)<f↑{-1}(Y↓2)=X↓2$. For each $p$ and~$q$ with $p+q=n$, there
is only one such partition with $|X↓1|=p$, $|X↓2|=q$: $X↓1={\bf p}$,
$X↓2={\bf n}-{\bf p}$. For each value of~$p$, there is a distinct set
of functions that map $X↓1$ into~$Y↓1$ and $X↓2$ into~$Y↓2$. The number
of such functions is
$$\#(n,i+j)=\sum↓{p+q=n}\#(p,i)\#(q,j)\,,$$
the {\sl convolution equation}, for the monotone subscripts mon, strict,
step, and iso. If $f$ is not required to be monotone, $X↓1=f↑{-1}(Y↓1)$ with
cardinality~$p$ can be chosen in ${n\choose p}$ different ways, so
$$\#(n,i+j)=\sum↓{p+q=n}{n\choose p}\#(p,i)\#(q,j)\,,$$
the {\sl binomial equation},
for the non-monotone subscripts all, inj, sur, and bij.

\vfill\eject

Setting $j=1$ in the convolution and binomial equations gives:
$$\eqalign{\#↓{\rm mon}(n,i+1)&=\sum↓{0≤p≤n}\#↓{\rm mon}(p,i)\cr
\noalign{\smallskip}
\#↓{\rm strict}(n,i+1)&=\#↓{\rm strict}(n-1,i)+\#↓{\rm strict}(n,i)\cr
\noalign{\smallskip}
\#↓{\rm step}(n,i+1)&=\sum↓{0≤p≤n-1}\#↓{\rm step}(p,i)\cr
\noalign{\smallskip}
\#↓{\rm iso}(n,i+1)&=\#↓{\rm iso}(n-1,i)\cr
\noalign{\smallskip}
\#↓{\rm all}(n,i+1)&=\sum↓{0≤p≤n}{n\choose p}\#↓{\rm all}(p,i)\cr
\noalign{\smallskip}
\#↓{\rm inj}(n,i+1)&={n\choose n-1}\#↓{\rm inj}(n-1,i)+{n\choose n}\#↓{\rm inj}(n,i)\cr
\noalign{\smallskip}
&=n\,\#↓{\rm inj}(n-1,i)+\#↓{\rm inj}(n,i)\cr
\noalign{\smallskip}
\#↓{\rm sur}(n,i+1)&=\sum↓{0≤p≤n-1}{n\choose p}\#↓{\rm sur}(p,i)\cr
\noalign{\smallskip}
\#↓{\rm bij}(n,i+1)&={n\choose n-1}\#↓{\rm bij}(n-1,i)\cr
\noalign{\smallskip}
&=n\,\#↓{\rm bij}(n-1,i)\cr}$$
These {\sl iterative equations\/} define $f(n,i+1)$ as linear combinations
of $f(o,i)$ through $f(n,i)$.

By subtracting $\#(n,i+1)$ from $\#(n+1,i+1)$, 
$$\eqalign{\#↓{\rm mon}(n+1,i+1)-\#↓{\rm mon}(n,i+1)&=\#↓{\rm mon}(n+1,i)\,,\cr
\#↓{\rm step}(n+1,i+1)-\#↓{\rm step}(n,i+1)&=\#↓{\rm step}(n,i)\,.\cr}$$
By induction on~$i$,

\smallskip
\display 20pt:$\bullet$:
$\#↓{\rm iso}(n,k)=\delta↓{n,k}$.

\smallskip
\display 20pt:$\bullet$:
$\#↓{\rm bij}(n,k)=\delta↓{n,k}(1\cdot 2\cdot 3\,\cdots\, n)$;
$\#↓{\rm bij}(n,n)=1\cdot 2\cdot 3\cdots n$, which by our earlier definition
is~$n!$ (multiplicative definition). Setting $n=i+j$ in the binomial equation 
for $\#↓{\rm bij}$
gives 
$$\eqalign{n!&={n\choose i}i!(n-i)!\,\cr
{n\choose i}&={n!\over i!\,(n-i)!}\qquad\hbox{(multiplicative definition).}\cr}$$

\noindent
With this formula, we may remodel the binomial equation as
$${\#(n,i+j)\over n!}=\sum↓{p+q=n}{\#(p,i)\over p!}\,{\#(q,j)\over q!}\,,$$
and defining $\underline{\#}(n,k)=\#(n,k)/n!$, the function
$\underline{\#}(n,k)$ 
with the non-monotone subscripts all, inj, sur, and bij
satisfies the convolution equation.

Similarly, the converse transformation converts the convolution equation into
the binomial equation; defining $\#!(n,k)=\#(n,k)n!$, it satisfies the
binomial equation. Iterative equations for $\underline{\#}$ are:
$$\eqalign{\underline{\#}↓{\rm all}(n,i+1)&=\sum↓{0≤p≤n}\underline{\#}↓{\rm all}
(p,i)/(n-p)!\cr
\noalign{\smallskip}
\underline{\#}↓{\rm inj}(n,i+1)&=\underline{\#}↓{\rm inj}(n-1,i)+
\underline{\#}↓{\rm inj}(n,i)\cr
\noalign{\smallskip}
\underline{\#}↓{\rm sur}(n,i+1)&=\sum↓{0≤p≤n-1}\underline{\#}↓{\rm sur}
(p,i)/(n-p)!\cr
\noalign{\smallskip}
\underline{\#}↓{\rm bij}(n,i+1)&=\underline{\#}↓{\rm bij}(n-1,i)\cr}$$
By the definition $k↑n=\#↓{\rm all}(n,k)$, the binomial equation becomes
the {\sl binomial theorem\/}:
$$(i+j)↑n=\sum↓{p+q=n}{n\choose p}i↑pj↑q\,.$$
Similarly, recalling $k↑{\underline{n}}=\#↓{\rm inj}(n,k)$, the binomial
equation becomes
$$(i+j)↑{\underline{n}}=\sum↓{p+q=n}{n\choose p}i↑{\underline{p}}j↑{\underline{q}}
\,.$$

A strictly monotone function is in 1--1 correspondence with its range, which is
an arbitrary subset of~{\bf k} with cardinality~$n$, so
$$\#↓{\rm strict}(n,k)={k\choose n}\,.$$
The iterative equation then yields
$${k\choose n}={k-1\choose n-1}+{k-1\choose n}\,,$$
the additive definition of ${k\choose n}$. 
The convolution equation gives
$${i+j\choose n}=\sum↓{p+q=n}{i\choose p}{j\choose q}\,.$$

For any function there is an associated equivalence relation:
$x↓1\sim x↓2$ iff $f(x↓1)=f(x↓2)$. There is a function $[x]$ that maps each
$x$ in ${\rm dom}\;f$ into its equivalence class, $\{\,u\mid f(u)=f(x)\,\}$.
Then $f$ can be expressed as the composition of~$p$, where 
$p(x)=[x]$, with a function~$q$ for which $q([x])=f(x)$, where $q$ is a
bijection. The number of partitions of~{\bf n} into $k$ nonempty equivalence
classes is the Stirling partition number $\{{n\atop k}\}$, and for each
there are $k!$~bijections onto~{\bf k}, so 
$\#↓{\rm sur}(n,k)=\{{n\atop k}\}k!$. Similarly,
$$k↑n=\#↓{\rm all}(n,k)=\sum↓i\left\{{n\atop i}\right\}
\#↓{\rm inj}(i,k)=\sum↓j\left\{{n\atop i}\right\}k↑{\underline{i}}\,.$$

If $f$ maps {\bf n+1} onto {\bf k+1}, it must map {\bf n} either onto {\bf k+1},
or onto {\bf k+1}$/\!\!/\{i\}$ for some~$i$. In the former case, $f(n+1)$ can
be chosen in $k+1$ ways; in the latter, $i$~can be chosen in $k+1$ ways.
but $f(n+1)$ must be~$i$. Therefore
$$\eqalign{\#↓{\rm sur}(n+1,k+1)&=(k+1)\bigl(\#↓{\rm sur}(n,k+1)+\#↓{\rm sur}(n,k)
\bigr)\cr
\left\{{n+1\atop k+1}\right\}(k+1)!&=(k+1)\left(\left\{{n\atop k+1}\right\}(k+1)!
+\left\{{n\atop k}\right\}k!\right)\cr
\left\{{n+1\atop k+1}\right\}&=(k+1)\left\{{n\atop k+1}\right\}+\left\{{n\atop k}
\right\}\,,\cr}$$
the additive definition of the Stirling partition numbers.

If $f$ is monotone from {\bf n} onto {\bf k}, then $f(1)=1$, $f(n)=k$, and
$f(x+1)$ is one of $f(x)$ or $f(x)+1$; $f$~is uniquely characterized by
the set of $k-1$ values of~$x$ out of {\bf n$\,$---$\,$1} 
for which $f(x+1)=f(x)+1$. Therefore
$$\#↓{\rm step}(n,k)={n-1\choose k-1}\,.$$
The convolution equation becomes
$${n-1\choose i+j-1}=\sum↓{p+q=n}{p-1\choose i-1}{q-1\choose j-1}$$
or, with a change of variables,
$$\sum↓{p+q=n}{p\choose i}{q\choose j}=\sum↓p{p\choose i}{n-p\choose j}={n+1\choose
i+j+1}\,.$$
Setting $j=0$,
$$\sum↓{0≤p≤n}{p\choose i}={n+1\choose i+1}\,.$$

Define $h(x)=f(x)+x$; a monotone $f$ from {\bf n} to {\bf k} corresponds
uniquely to a strictly monotone~$h$ from~{\bf n} to {\bf k+n--1}, so
$\#↓{\rm mon}(n,k)={k+n-1\choose n}$.
The iterative and convolution equations for $\#↓{\rm mon}$ are therefore
those for $\#↓{\rm strict}$ except for a change of variables.
The {\sl rising factorial power\/} $k↑{\underline{n}}$ is defined as
$(k+n-1)!/(k-1)!=\#!↓{\rm mon}(n,k)$; it satisfies the binomial equation
$$(i+j)↑{\overline{n}}=\sum↓{p+q=n}{n\choose p}i↑{\overline{p}}j↑{\overline{q}}\,.$$

Next we tabulate all but the most trivial $\#(n,k)$ for $0≤\{n,k\}≤5$.

$$\vtop{\offinterlineskip
\halign{$#$\quad%
&\vrule#&\strut\quad$\hfil#$&\quad$\hfil#$&\quad$\hfil#$&\quad$\hfil#$%
&\quad$\hfil#$&\quad$\hfil#$\quad\cr
&\omit&\multispan6\hfil$\#↓{\rm all}=k↑n$\hfil\cr
\noalign{\smallskip}
&\omit&0&1&2&3&4&5\cr
&\omit&\multispan6\hrulefill\cr
&height2pt\cr
0&&1&1&1&1&1&1\cr
1&&0&1&2&3&4&5\cr
2&&0&1&4&9&16&25\cr
3&&0&1&8&27&64&125\cr
4&&0&1&16&81&256&625\cr
5&&0&1&32&243&1024&3125\cr
}}\qquad
\vtop{\offinterlineskip
\halign{$#\hfil$\cr
\#↓{\rm iso}=\delta↓{nk}\cr
\noalign{\smallskip}
\#↓{\rm bij}=\delta↓{nk}n!\cr
}}$$

$$\vbox{\offinterlineskip
\halign{$#$\quad%
&\vrule#&\strut\quad$\hfil#$&\quad$\hfil#$&\quad$\hfil#$&\quad$\hfil#$%
&\quad$\hfil#$&\quad$\hfil#$\quad\cr
&\omit&\multispan6\hfil$\#↓{\rm inj}=k↑{\underline{n}}$\hfil\cr
\noalign{\smallskip}
&\omit&0&1&2&3&4&5\cr
&\omit&\multispan6\hrulefill\cr
&height2pt\cr
0&&1&1&1&1&1&1\cr
1&&0&1&2&3&4&5\cr
2&&0&0&2&6&12&20\cr
3&&0&0&0&6&24&60\cr
4&&0&0&0&0&24&120\cr
5&&0&0&0&0&0&120\cr
}}\qquad
\vbox{\offinterlineskip
\halign{$#$\quad%
&\vrule#&\strut\quad$\hfil#$&\quad$\hfil#$&\quad$\hfil#$&\quad$\hfil#$%
&\quad$\hfil#$&\quad$\hfil#$\quad\cr
&\omit&\multispan6\hfil$\underline{\#}↓{\rm inj}=\#↓{\rm strict}={k\choose n}$\hfil\cr
\noalign{\smallskip}
&\omit&0&1&2&3&4&5\cr
&\omit&\multispan6\hrulefill\cr
&height2pt\cr
0&&1&1&1&1&1&1\cr
1&&0&1&2&3&4&5\cr
2&&0&0&1&3&6&10\cr
3&&0&0&0&1&4&10\cr
4&&0&0&0&0&1&5\cr
5&&0&0&0&0&0&1\cr
}}$$

$$\vbox{\offinterlineskip
\halign{$#$\quad%
&\vrule#&\strut\quad$\hfil#$&\quad$\hfil#$&\quad$\hfil#$&\quad$\hfil#$%
&\quad$\hfil#$&\quad$\hfil#$\quad\cr
&\omit&\multispan6\hfil$\#↓{\rm sur}=\{{n\atop k}\}k!$\hfil\cr
\noalign{\smallskip}
&\omit&0&1&2&3&4&5\cr
&\omit&\multispan6\hrulefill\cr
&height2pt\cr
0&&1&0&0&0&0&0\cr
1&&0&1&0&0&0&0\cr
2&&0&1&2&0&0&0\cr
3&&0&1&6&6&0&0\cr
4&&0&1&14&36&24&0\cr
5&&0&1&30&150&240&120\cr
}}\qquad
\vbox{\offinterlineskip
\halign{$#$\quad%
&\vrule#&\strut\quad$\hfil#$&\quad$\hfil#$&\quad$\hfil#$&\quad$\hfil#$%
&\quad$\hfil#$&\quad$\hfil#$\quad\cr
&\omit&\multispan6\hfil$\underline{\#}↓{\rm sur}=\{{n\atop k}\}k!/n!$\hfil\cr
\noalign{\smallskip}
&\omit&0&1&2&3&4&5\cr
&\omit&\multispan6\hrulefill\cr
&height2pt\cr
0&&1&0&0&0&0&0\cr
1&&0&1&0&0&0&0\cr
2&&0&1/2&1&0&0&0\cr
3&&0&1/6&1&1&0&0\cr
4&&0&1/24&7/12&3/2&1&0\cr
5&&0&1/120&1/4&5/4&2&1\cr
}}$$

$$\vbox{\offinterlineskip
\halign{$#$\quad%
&\vrule#&\strut\quad$\hfil#$&\quad$\hfil#$&\quad$\hfil#$&\quad$\hfil#$%
&\quad$\hfil#$&\quad$\hfil#$\quad\cr
&\omit&\multispan6\hfil$\#↓{\rm mon}={k+n-1\choose n}$\hfil\cr
\noalign{\smallskip}
&\omit&0&1&2&3&4&5\cr
&\omit&\multispan6\hrulefill\cr
&height2pt\cr
0&&1&1&1&1&1&1\cr
1&&0&1&2&3&4&5\cr
2&&0&1&3&6&10&15\cr
3&&0&1&4&10&20&35\cr
4&&0&1&5&15&35&70\cr
5&&0&1&6&21&56&126\cr
}}\qquad
\vbox{\offinterlineskip
\halign{$#$\quad%
&\vrule#&\strut\quad$\hfil#$&\quad$\hfil#$&\quad$\hfil#$&\quad$\hfil#$%
&\quad$\hfil#$&\quad$\hfil#$\quad\cr
&\omit&\multispan6\hfil$\#↓{\rm step}={n-1\choose k-1}$\hfil\cr
\noalign{\smallskip}
&\omit&0&1&2&3&4&5\cr
&\omit&\multispan6\hrulefill\cr
&height2pt\cr
0&&1&0&0&0&0&0\cr
1&&0&1&0&0&0&0\cr
2&&0&1&1&0&0&0\cr
3&&0&1&2&1&0&0\cr
4&&0&1&3&3&1&0\cr
5&&0&1&4&6&4&1\cr
}}$$

For some subsets of $F$, we get further identities by partitioning {\bf n}
into $X↓1={\bf p}$ and $X↓2={\bf n}/\!\!/{\bf p}$, where $q=n-p$.
For $f\in F$, the number of restrictions of~$f$ to~$X↓1$ and~$X↓2$ is
$\#↓{\rm all}(p,k)$ and $\#↓{\rm all}(q,k)$ respectively, so
$$\eqalign{k↑{p+q}&=k↑pk↑q\cr
k↑{p+1}&=k\,k↑p\,.\cr}$$
By classifying the monotone functions from {\bf p+q--1} to {\bf k+1} according
to the value $f(p)=i+1$,
$$\#↓{\rm mon}(p+q-1,k+1)=\sum↓{i+j=k}\#↓{\rm mon}(p-1,i+1)\#↓{\rm mon}
(q-1,j+1)\,,$$
a close relative of the convolution equation. Notice that the summation
is on the second argument. Similarly,
$$\eqalign{\#↓{\rm strict}(p+q-1,k-1)&=\sum↓{i+j=k}\#↓{\rm strict}(p-1,i-1)
\#↓{\rm strict}(q-1,j-1)\cr
\noalign{\smallskip}
\#↓{\rm step}(p+q+1,k+1)&=\sum↓{i+j=k}\#↓{\rm step}(p+1,i+1)
\#↓{\rm step}(q+1,j+1)\,.\cr}$$
Define
$$\eqalign{\phi↓{\rm mon}(n,k)&=\#↓{\rm mon}(n-1,k+1)\,,\cr
\#↓{\rm mon}(n,k)&=\phi↓{\rm mon}(n+1,k-1)\,;\cr
\noalign{\smallskip}
\phi↓{\rm strict}(n,k)&=\#↓{\rm strict}(n-1,k-1)\,,\cr
\#↓{\rm strict}(n,k)&=\phi↓{\rm strict}(n+1,k+1)\,;\cr
\noalign{\smallskip}
\phi↓{\rm step}(n,k)&=\#↓{\rm step}(n+1,k+1)\,,\cr
\#↓{\rm step}(n,k)&=\phi↓{\rm step}(n-1,k-1)\,.\cr}$$
Then $\phi↓{\rm mon}(n,k)={k+n-1\choose n-1}$, 
$\phi↓{\rm strict}(n,k)={k-1\choose n-1}$, and 
$\phi↓{\rm step}(n,k)={n-2\choose k-2}$ satisfy the reversed
convolution equation $\phi(p+q,k)=\sum↓{i+j=k}\phi(p,i)\phi(q,j)$ for
those subscripts.

The convolution equation is the equation for a coefficient in the product
of two polynomials or power series; if
$$\biggl(\sum↓pa↓px↑p\biggr)\biggl(\sum↓qb↓qx↑q\biggr)=\sum↓nc↓nx↑n\,,$$
then
$$c↓n=\sum↓{p+q=n}a↓pb↓q\,.$$
For each function $\#(n,k)$ or $\underline{\#}(n,k)$ satisfying the convolution
equation, $\sum↓p\#(p,i)x↑p$ can be interpreted
as a power series, $g↓i(x)$,
of which the coefficients are the $i↑{\rm th}$ column in the table. The
convolution equation says that $g↓{i+j}=g↓ig↓j$, or more simply that
$g↓i=(g↓1)↑i$.

Tabulating,
$$\vcenter{\halign{$#\hfil$\qquad&$\displaystyle{\hfil#\hfil}$\qquad%
&$\displaystyle{\hfil#\hfil}$\cr
{\rm Subscript}&g↓1&g↓i\cr
\noalign{\medskip}
\underline{\#}↓{\rm all}&\sum {x↑p\over p!}=e↑x&e↑{ix}\cr
\noalign{\smallskip}
\underline{\#}↓{\rm inj}&1+x&(1+x)↑i\cr
\noalign{\smallskip}
\underline{\#}↓{\rm sur}&\sum↓{p≥1}{x↑p\over p!}=e↑x-1&(e↑x-1)↑i=\sum↓{a+b=i}
{i\choose a}e↑{ax}(-1)↑b\cr
\noalign{\smallskip}
\underline{\#}↓{\rm bij}&x&x↑i\cr
\noalign{\smallskip}
\#↓{\rm mon}&{1\over 1-x}&(1-x)↑{-i}\cr
\noalign{\smallskip}
\#↓{\rm strict}&1+x&(1+x)↑i\cr
\noalign{\smallskip}
\#↓{\rm step}&{x\over 1-x}&\left({x\over 1-x}\right)↑i\cr
\noalign{\smallskip}
\#↓{\rm iso}&x&x↑i\cr}}$$

The most illuminating fact arising from the table above is that
$$\eqalign{\underline{\#}↓{\rm sur}(n,k)&=\sum↓{a+b=k}{k\choose a}\,
{a↑n\over n!}\,(-1)↑b\,,\cr
\noalign{\smallskip}
\#↓{\rm sur}(n,k)&=\sum↓a{k\choose a}\,a↑n(-1)↑{k-a}\,,\cr}$$
which is the $k↑{\rm th}$ difference of $a↑n$, evaluated at $a=0$.

Applying the binomial theorem to $g↓i$ for $\#↓{\rm mon}$,
$${k+n-1\choose n}=\#↓{\rm mon}(n,k)={-k\choose n}(-1)↑n\,,$$
suggesting defining
$${-k\choose n}=(-1)↑n{k+n-1\choose n}\,.$$

All of the $g↓i$ except $\underline{\#}↓{\rm all}$ and 
$\underline{\#}↓{\rm sur}$ are rational functions. This fact gives
rise to a linear recurrence. For example, $g↓{1\,{\rm step}}$ is
${x\over 1-x}$, $g↓{i+1}\cdot(1-x)=g↓i\cdot x$, so
$\#↓{\rm step}(n,i+1)-\#↓{\rm step}(n-1,i+1)=\#↓{\rm step}(n-1,i)$.
This yields
$$\#↓{\rm step}(n,i+1)=\#↓{\rm step}(n-1,i+1)+\#↓{\rm step}(n-1,i)\,.$$

[RWF: following is incomplete.]

We can similarly associate power series with $\phi↓{\rm mono}$, 
$\phi↓{\rm strict}$, and $\phi↓{\rm step}$. Let
$\gamma↓n(y)=\sum y↑i\phi(n,i)$.
Then $\gamma↓n=(\gamma↓1)↑n$,
$$\vcenter{\halign{#\hfil\qquad&$\displaystyle{\hfil#\hfil}$\qquad%
&$\displaystyle{\hfil#\hfil}$\cr
Subscript&\gamma↓1&\gamma↓n\cr
\noalign{\medskip}
mon&{1\over 1-y}&(1-y)↑{-n}\cr
\noalign{\smallskip}
&\hbox{? or }{1\over y(1-y)}\cr
\noalign{\smallskip}
strict\cr
\noalign{\smallskip}
step\cr
}}$$




\bigskip
\parindent0pt
\copyright 1987 Robert W. Floyd.
First draft (not published)
September 9, 1987.
%revised date;
%subsequently revised.

\bye